Exercise 7 (Homework 6).
(R (decidable/recursive languages),
RE (semi-decidable/ recursively enumerable languages))
On the image of decidable sets
- Show that if C\in \mathbf{RE} and f is a computable function, then f(C)\in \mathbf{RE}.
- Show that the previous sentence is not true if we substitute \mathbf{RE} for \mathbf{R}. That is, show that there is a set C\in \mathbf{R} and a computable function f such that f(C)\notin \mathbf{R}.
- Show that there is a set C\in \mathbf{R} and a total computable function f such that f(C)\notin \mathbf{R}.